package sword.offer;

import org.junit.Test;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
 * 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Eleven {
    // 但凡涉及到排序相关的 都应该优先考虑二分查找
    class Solution {
        public int minArray(int[] numbers) {
            /**
             *  经过观察，数组旋转后分为两组递增的数据。即查找第一组和第二组的分界即可。
             *  值得注意的是，数组可能存在重复的数
             * */
            int left = 0, right = numbers.length-1;
            while(left < right){
                int mid = left + (right-left)/2;
                // 当中间的数小于右边的数 则分界在左边(包含mid 因为mid有可能最小)
                if(numbers[mid] < numbers[right]) {
                    right = mid;
                }
                // 当中间的数大于右边的数，那么分界在右部分（不包含mid 因为mid不可能最小)
                else if(numbers[mid] > numbers[right]) {
                    left = mid+1;
                }
                // 当中间的数==右边的数，不知道在哪边，右指针缩减范围
                else if(numbers[mid] == numbers[right]){
                    right--;
                }
            }
            return numbers[left];
        }
    }
}
